The recursive breakdown of Quick Sort into smaller subproblems reveals a critical dependency: the size and balance of the two resultant partitions. Quick Sort's performance is critically sensitive to the pivot selection strategy.
- If the pivot consistently divides the input array $A$ of size $n$ into roughly equal halves (an $n/2$ split), the recurrence relation leads to the optimal average time complexity of $O(n \log n)$.
- Conversely, if the pivot is repeatedly chosen poorly—such as always selecting the smallest or largest element—the array is split into $0$ elements and $n-1$ elements.
- This unbalanced split results in $n$ levels of recursion, leading directly to the worst-case complexity of $O(n^2)$.
- The primary goal of any robust pivot strategy is to minimize the probability of encountering this $O(n^2)$ scenario by ensuring the pivot is close to the true median of the segment.
| Strategy | Selection Method | Average Case | Worst Case Risk |
|---|---|---|---|
| Fixed (e.g., First/Last) | Always $A[low]$ or $A[high]$ | $O(n \log n)$ | High (especially on sorted data) |
| Randomized Pivot | Select a random index $p_{index}$ in the segment | $O(n \log n)$ | Very Low (Non-deterministic $O(n^2)$) |
| Median-of-Three | Select median of $A[low], A[mid], A[high]$ | $O(n \log n)$ | Low (Best practical choice for balance) |